package java_thinking.unit_21.concurrentutil;

/**
 * @Desc:
 *      1.ConcurrentHashMap: 必看 https://blog.csdn.net/lengxiao1993/article/details/84029155
 *                              https://www.cnblogs.com/kkdn/p/9039618.html
 *                              https://mp.weixin.qq.com/s/rlyoQp4ngTX8mjGDJgJIRA 提问比较好
 *          1 Node：
 *            核心的内部类，对value和next属性设置了volatile同步锁，不允许调用setValue方法直接改变Node的value域，它增加了
 *            find 方法辅助map.get()方法。
 *
 *          2 sizeCtl：
 *            1.1 负数代表正在进行初始化或扩容操作
 *            1.2 -1代表正在初始化
 *            1.3 -N 表示有N-1个线程正在进行扩容操作
 *            1.4 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。
 *
 *          3 TreeNode：**************
 *            当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点
 *            包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap集成自Node类，
 *            而并非HashMap中的集成自LinkedHashMap.Entry<K,V>类，也就是说TreeNode带有next指针，这样做的目的是方便基于
 *            TreeBin的访问。
 *
 *          4 TreeBin：***************
 *            这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实
 *            际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还
 *            带有了读写锁。
 *
 *          5 ForwardingNode：
 *            一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针
 *            全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。
 *
 *          6 三个核心方法：
 *            1 tabAt(Node<K,V>[] tab, int i)                               获得在i位置上的Node节点
 *            2 casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v)  利用CAS算法设置i位置上的Node节点
 *            3 setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)               利用volatile方法设置节点位置的值
 *
 *          7 Unsafe类提供了一些硬件级别的原子操作:
 *            1.1 arrayBaseOffset(Class class)：获取数组第一个元素的偏移地址
 *            1.2 arrayIndexScale(Class class)：获取数组中元素的增量地址。
 *            1.3 getObjectVolatile(Object obj, long offset)：获取obj对象中offset偏移地址对应的Object型field属性值，支持
 *                Volatile读内存语义。
 *
 *          8.put 步骤
 *            1 校验key value 值，都不能是null。这点和 HashMap 不同。
 *            2 得到 key 的 hash 值。
 *            3 死循环并更新 tab 变量的值。
 *            4 如果容器没有初始化，则初始化。调用 initTable 方法。该方法通过一个变量 + CAS 来控制并发。
 *            5 根据 hash 值找到数组下标，如果对应的位置为空，就创建一个 Node 对象用CAS方式添加到容器。并跳出循环。
 *            6 如果 hash 冲突，也就是对应的位置不为 null，则判断该槽是否被扩容了（-1 表示被扩容了），如果被扩容了，返回新
 *              的数组。
 *            7 如果 hash 冲突 且 hash 值不是 -1，表示没有被扩容。则进行链表操作或者红黑树操作，注意，这里的 f 头节点被锁
 *              住了，保证了同时只有一个线程修改链表。防止出现链表成环。
 *            8 和 HashMap 一样，如果链表树超过8，则修改链表为红黑树。
 *            9 将数组加1（CAS方式），如果需要扩容，则调用 transfer 方法进行移动和重新散列，该方法中，如果是槽中只有单个节点，
 *              则使用CAS直接插入，如果不是，则使用 synchronized 进行同步，防止并发成环。
 *            0 如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能
 *              被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助
 *              进行扩容；
 *
 *          9.transfer()扩容
 *            3.1 通过计算 CPU 核心数和 Map 数组的长度得到每个线程（CPU）要帮助处理多少个桶，并且这里每个线程处理都是平均的
 *                。默认每个线程处理 16 个桶。因此，如果长度是 16 的时候，扩容的时候只会有一个线程扩容。
 *            3.2 初始化临时变量 nextTable。将其在原有基础上扩容两倍。
 *            3.3 死循环开始转移。多线程并发转移就是在这个死循环中，根据一个 finishing 变量来判断，该变量为 true 表示扩容结
 *                束，否则继续扩容。
 *                  1 进入一个 while 循环，分配数组中一个桶的区间给线程，默认是 16. 从大到小进行分配。当拿到分配值后，进行
 *                    i-- 递减。这个 i 就是数组下标。（其中有一个 bound 参数，这个参数指的是该线程此次可以处理的区间的最小
 *                    下标，超过这个下标，就需要重新领取区间或者结束扩容，还有一个 advance 参数，该参数指的是是否继续递减转
 *                    移下一个桶，如果为 true，表示可以继续向后推进，反之，说明还没有处理好当前桶，不能推进)
 *                  2 出 while 循环，进 if 判断，判断扩容是否结束，如果扩容结束，清空临时变量，更新 table 变量，更新库容阈
 *                    值。如果没完成，但已经无法领取区间（没了），该线程退出该方法，并将 sizeCtl 减一，表示扩容的线程少一个
 *                    了。如果减完这个数以后，sizeCtl 回归了初始状态，表示没有线程再扩容了，该方法所有的线程扩容结束了。
 *                    （这里主要是判断扩容任务是否结束，如果结束了就让线程退出该方法，并更新相关变量）。然后检查所有的桶，
 *                    防止遗漏。
 *                  3 如果没有完成任务，且 i 对应的槽位是空，尝试 CAS 插入占位符，让 putVal 方法的线程感知。
 *                  4 如果 i 对应的槽位不是空，且有了占位符，那么该线程跳过这个槽位，处理下一个槽位
 *                  5 如果以上都是不是，说明这个槽位有一个实际的值。开始同步处理这个桶。
 *                  6 到这里，都还没有对桶内数据进行转移，只是计算了下标和处理区间，然后一些完成状态判断。同时，如果对应下
 *                    标内没有数据或已经被占位了，就跳过了。
 *            3.4 处理每个桶的行为都是同步的。防止 putVal 的时候向链表插入数据。
 *                1 如果这个桶是链表，那么就将这个链表根据 length 取于拆成两份，取于结果是 0 的放在新表的低位，取于结果是1
 *                  放在新表的高位。
 *                2 如果这个桶是红黑数，那么也拆成 2 份，方式和链表的方式一样，然后，判断拆分过的树的节点数量，如果数量小
 *                  于等于 6，改造成链表。反之，继续使用红黑树结构。
 *                3 到这里，就完成了一个桶从旧表转移到新表的过程。
 *            精简，分成 5 步骤：
 *            单线程流程：
 *              1 首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素：
 *              2 如果这个位置为空，就在原table中的i位置放入forwardNode节点，这个也是触发并发扩容的关键点；
 *              3 如果这个位置是Node节点（fh>=0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上
 *              4 如果这个位置是TreeBin节点（fh<0），也做一个反序处理，并且判断是否需要untreefi，把处理的结果分别放在nextTable的i和i+n的位置上
 *              5 遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0.75倍 ，完成扩容。
 *            对多线程的支持：！！！
 *              遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，
 *              处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作。
 *              而且还很好的解决了线程安全的问题。！！！
 *
 *         10.helpTransfer():
 *            这是一个协助扩容的方法。这个方法被调用的时候，当前ConcurrentHashMap一定已经有了nextTable对象，首先拿到这个
 *            nextTable对象，调用transfer方法。回看上面的 transfer 方法可以看到，当本线程进入扩容方法的时候会直接进入复制阶段。
 *
 *         11.treeifyBin方法:
 *            这个方法用于将过长的链表转换为TreeBin对象。但是他并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要
 *            求，直接进行扩容操作并返回；如果满足条件才链表的结构抓换为TreeBin ，这与HashMap不同的是，它并没有把TreeNode直
 *            接放入红黑树，而是利用了TreeBin这个小容器来封装所有的TreeNode.
 *
 *         12.size()****************
 *            对于ConcurrentHashMap来说，这个table里到底装了多少东西其实是个不确定的数量，因为不可能在调用size()方法的时候
 *            像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值。对于这个估计值，
 *            ConcurrentHashMap也是大费周章才计算出来的。
 *            1 addCount():
 *              在put方法结尾处调用了addCount方法，把当前ConcurrentHashMap的元素个数+1这个方法一共做了两件事,更新baseCount
 *              的值，检测是否进行扩容。
 *
 *         总结:
 *              1 JDK6,7中的ConcurrentHashMap主要使用Segment来实现减小锁粒度，把HashMap分割成若干个Segment，在put的时候需
 *                要锁住Segment，get时候不加锁，使用volatile来保证可见性，当要统计全局时（比如size），首先会尝试多次计算
 *                modcount 来确定，这几次尝试中，是否有其他线程进行了修改操作，如果没有，则直接返回size。如果有，则需要依次锁
 *                住所有的Segment来计算。
 *              2 jdk7中ConcurrentHashMap中，当长度过长碰撞会很频繁，链表的增改删查操作都会消耗很长的时间，影响性能,所以jdk8
 *                中完全重写了concurrentHasMap,代码量从原来的1000多行变成了6000多行，实现上也和原来的分段式存储有很大的区别。
 *              3 主要设计上的变化有以下几点:
 *                1 不采用segment而采用node，锁住node来实现减小锁粒度。
 *                2 设计了MOVED状态 当resize的中过程中 线程2还在put数据，线程2会帮助resize。
 *                3 使用3个 CAS 操作来确保 node 的一些操作的原子性，这种方式代替了锁。
 *                4 sizeCtl 的不同值来代表不同含义，起到了控制的作用。
 *                5 至于为什么 jdk8 中使用 synchronized 而不是ReentrantLock，我猜是因为JDK8中对synchronized有了足够的优化吧。
 *      2.
 *
 * @author: cww
 * @DateTime: 2019/7/18 19:17
 */

/**
 *      2.ConcurrentLinkedQueue：必看 https://blog.csdn.net/qq_38293564/article/details/80798310
 *          1.入队出队快照+流程见visio图;
 *          2.peek操作会改变head指向，执行peek()方法后head会指向第一个具有非空元素的节点。
 *          3.size()方法用来获取当前队列的元素个数，但在并发环境中，其结果可能不精确
 *          4.contains(Object o)方法和size方法类似，有可能返回错误结果，比如调用该方法时，元素还在队列里面，但是遍历过程中，
 *            该元素被删除了，那么就会返回false。
 *          5.使用 CAS 原子指令来处理对数据的并发访问，这是非阻塞算法得以实现的基础。
 *          6.head/tail 并非总是指向队列的头 / 尾节点，也就是说允许队列处于不一致状态。 这个特性把入队 / 出队时，原本需要一
 *            起原子化执行的两个步骤分离开来，从而缩小了入队 / 出队时需要原子化更新值的范围到唯一变量。这是非阻塞算法得以实现
 *            的关键。
 *          7.由于队列有时会处于不一致状态。为此，ConcurrentLinkedQueue 使用三个不变式来维护非阻塞算法的正确性。
 *          8.以批处理方式来更新 head/tail，从整体上减少入队 / 出队操作的开销。
 *          9.为了有利于垃圾收集，队列使用特有的 head 更新机制；为了确保从已删除节点向后遍历，可到达所有的非删除节点，队列使
 *            用了特有的向后推进策略。
 *          10.size()不加锁
 *          11.三个不变式：
 *              1.基本不变式：
 *                  在执行方法之前和之后，队列必须要保持的不变式：
 *                      当入队插入新节点之后，队列中有一个 next 域为 null 的（最后）节点。
 *                      从 head 开始遍历队列，可以访问所有 item 域不为 null 的节点。
 *              2.head 的不变式和可变式
 *                  在执行方法之前和之后，head 必须保持的不变式：
 *                      所有“活着”的节点（指未删除节点），都能从 head 通过调用 succ() 方法遍历可达。
 *                      head 不能为 null。
 *                      head 节点的 next 域不能引用到自身。
 *                  在执行方法之前和之后，head 的可变式：
 *                      head 节点的 item 域可能为 null，也可能不为 null。
 *                      允许 tail 滞后（lag behind）于 head，也就是说：从 head 开始遍历队列，不一定能到达 tail。
 *              3.tail 的不变式和可变式：
 *                  在执行方法之前和之后，tail 必须保持的不变式：
 *                      通过 tail 调用 succ() 方法，最后节点总是可达的。
 *                      tail 不能为 null。
 *                  在执行方法之前和之后，tail 的可变式：
 *                      tail 节点的 item 域可能为 null，也可能不为 null。
 *                      允许 tail 滞后于 head，也就是说：从 head 开始遍历队列，不一定能到达 tail。
 *                      tail 节点的 next 域可以引用到自身。
 *
 *        问：
 *          1.tail的极限位置为什么是4个？
 *          2.tail为什么不作为最后一个节点？
 *
 *          总结：
 *              1 为什么不再每次入队时都更新tail节点的思考：
 *                在JDK 1.7的实现中，doug lea使用hops变量来控制并减少tail节点的更新频率，并不是每次节点入队后都将 tail节点更
 *                新成尾节点，而是当tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距
 *                离越长使用CAS更新tail节点的次数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因
 *                为循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来看它通过增加对volatile变
 *                量的读操作来减少了对volatile变量的写操作，而对volatile变量的写操作开销要远远大于读操作，所以入队效率会有所
 *                提升。在JDK 1.8的实现中，tail的更新时机是通过p和t是否相等来判断的，其实现结果和JDK 1.7相同，即当tail节点和
 *                尾节点的距离大于等于1时，更新tail。
 *              2 它使用 CAS 原子指令来处理对数据的并发访问。同时，它允许队列处于不一致状态。这个特性分离了入队 / 出队操作中
 *                包含的两个需要一起原子执行的步骤，从而有效的缩小了入队 / 出队时的原子化（更新值的）范围为唯一变量。由于队
 *                列可能处于不一致状态，为此 ConcurrentLinkedQueue 使用三个不变式来维护非阻塞算法的正确性。
 */

/**
 *      3.ConcurrentLinkedDeque：https://segmentfault.com/a/1190000016284649
 *          1.入队出队快照+流程见visio图;
 *          2.与ConcurrentLinkedQueue一样，每次跳2个结点的方式移动指针，这主要考虑到并发环境以这种hop跳的方式可以提升效率。
 *          3.三个不变性：
 *            1 head/tail 的不变性：
 *              1.1 第一个节点总是能以O(1)的时间复杂度从 head 通过 prev 链接到达；
 *              1.2 最后一个节点总是能以O(1)的时间复杂度从 tail 通过 next 链接到达；
 *              1.3 所有live节点（item不为null的节点），都能从第一个节点通过调用 succ() 方法遍历可达；
 *              1.4 所有live节点（item不为null的节点），都能从最后一个节点通过调用 pred() 方法遍历可达；
 *              1.5 head/tail 不能为 null；
 *              1.6 head  节点的 next 域不能引用到自身；
 *              1.7 head/tail 不会是GC-unlinked节点（但它可能是unlink节点）。
 *            2 head/tail的可变性：
 *              2.1 head/tail 节点的 item 域可能为 null，也可能不为 null；
 *              2.2 head/tail 节点可能从first/last/tail/head 节点访问时不可达；
 *              2.3 tail 节点的 next 域可以引用到自身。
 *          4.CLD中对Node的定义：
 *            4.1 live node：节点的 item!=null 被称为live节点。当节点的 item 被 CAS 改为 null，逻辑上来讲这个节点已经从链表
 *                中移除；一个新的元素通过 CAS 添加到一个包含空 prev 或空 next 的 first 或 last 节点，这个元素的节点在这时
 *                是 live节点。
 *            4.2 first node & last node：首节点(first node)总会有一个空的 prev 引用，终止任何从 live 节点开始的 prev 引
 *                用链；同样的最后一个节点(last node)是 next 的终止节点。first/last 节点的 item 可以为 null。并且 first 和
 *                last 节点总是相互可达的。
 *            4.3 active node：live节点、first/last 节点也被称为活跃节点(active node)，活跃节点一定是被链接的，如果p节点
 *                为active节点，则：p.item != null || (p.prev == null && p.next != p) || (p.next == null && p.prev != p)
 *            4.4 self-node：自链接节点，prev 或 next 指向自身的节点，自链接节点用在解除链接操作中，并且它们都不是active
 *                node。
 *            4.5 head/tail节点：head/tail 也可能不是 first/last 节点。从 head 节点通过 prev 引用总是可以找到 first 节点，
 *                从 tail 节点通过 next 引用总是可以找到 last 节点。允许 head 和 tail 引用已删除的节点，这些节点没有链接，
 *                因此可能无法从 live 节点访问到。
 *
 *
 *          4.节点删除时经历三个阶段：逻辑删除(logical deletion)，未链接( unlinking)，和gc未链接( gc-unlinking)：
 *              1 logical deletion：通过 CAS 修改节点 item 为 null 来完成，表示当前节点可以被解除链接(unlinking)。
 *              2 unlinking： 这种状态下的节点与其他 active 节点有链接，但是其他 active 节点与之都没有链接，也就是说从这个
 *                状态下的节点可以达到 active 节点，但是从 active 节点不可达到这种状态的节点。在任何时候，从 first 通过 next
 *                找到的 live 节点和从 last 通过 prev 找到的节点总是相等的。但是，在节点被逻辑删除时上述结论不成立，这些被逻
 *                辑删除的节点也可能只从一端是可达的。
 *              3 gc-unlinking： GC未链接使已删除节点不可达到 active 节点，使GC更容易回收被删除的节点。通过让节点自链接或
 *                链接到终止节点（PREV_TERMINATOR 或 NEXT_TERMINATOR）来实现。 gc-unlinking 节点从 head/tail 访问不可达。
 *                这一步是为了使数据结构保持GC健壮性(gc-robust)，防止保守式GC（conservative GC，目前已经很少使用）对这些边
 *                界空间的使用。对保守式GC来说，使数据结构保持GC健壮性会消除内存无限滞留的问题，同时也提高了分代收机器的性能。
 *
 *          5.入队条件：p.prev==null&&p.next!=p即：前驱为空且后继非引用自己；
 *
 *          6.出队条件：找到fist节点p.prev==null&&p.next!=p,若first节点为空则找后继不为空节点,逻辑删再unlink
 */

/**
 *      4.LinkedBlockingDeque 见VISIO xmind
 *          1.独占锁阻塞队列-生产生消费者模型；
 *          2.底层 Node 单向链表
 *          3.使用原子变量计数
 *          4.使用Condition实现阻塞队列
 *          5.进出队列分别使用各自的ReentrantLock
 *
 */

/**
 *      5.ArrayBlockingQueue<E> 见VISIO xmind
 */

/**
 *      6.PriorityBlockingQueue<E> 见 xmind  未深入
 */

/**
 *      5.SynchronousQueue  见 xmind  未深入
 *          https://www.cnblogs.com/dwlsxj/p/Thread.html
 */

/**
 *      6.DelayedWorkQueue<V> 见 xmind visio  未深入
 */

public class CollectionTheory {
}
